1. The Field of the Invention
The present invention relates to the field of memory management. In particular, the present invention relates to the methods and systems for managing heap creation and allocation in a manner that improves memory usage and reduces the risk of virtual memory fragmentation.
2. Background and Related Art
Computers have transformed the lives of many in this modern era. The ability to store and retrieve instructions and data is fundamental to computer operation. Modern computer systems access physical memory through a virtual memory manager that maps virtual memory addresses to physical memory addresses. During run time, applications identify the virtual memory address that is to be operated on. Typical operations might include reading information from the identified virtual memory address, writing information to that address, allocating the address, releasing the address for further use, and so forth. The virtual memory manager then converts the virtual memory address into a corresponding physical memory so that the appropriate operation may be performed on the appropriate physical address.
The amount of available virtual memory is not limited to the amount of available physical memory. When the physical memory is full, the virtual memory manager transfers or xe2x80x9cpagesxe2x80x9d some of the memory contents to disk. When a virtual memory address that has been paged to disk is accessed, the virtual memory manager loads the corresponding information from the disk back into the physical memory. The process of transferring memory between the physical memory and the disk is called xe2x80x9cswappingxe2x80x9d. This process allows the virtual memory to be much larger than the physical memory.
The number of virtual memory addresses is, however, limited by the bit size of the address space used to address virtual memory. For example, in an operating system that uses 32-bit virtual memory addressing, the number of virtual memory addresses is limited to 232 or 4 Gig, where 1 Gig is equal to 1024 Meg, where 1 Meg is equal to 220 or 1048,576. Since each address contains one byte of information, the virtual memory size is limited to 4 Gigabytes (GB). Typically, an operating system will internally reserve 1 or 2 GB of virtual memory for the operating system leaving only 2 or 3 GB of virtual memory for non-system processes to use. While this may seem like a lot of memory, as software applications are becoming more complex, virtual memory allocations may use the entire available virtual memory.
The virtual memory manager allocates virtual memory segments at a relatively large granularity. In this description and in the claims, a xe2x80x9cvirtual memory segmentxe2x80x9d is defined as a group of contiguous virtual memory addresses. For example, a typical granularity of a virtual memory segment allocated by the virtual memory manager is 64 kilobytes (KB). In this case, the smallest virtual segment that could be allocated by the virtual memory manager would be 64 KB. However, many applications require much less virtual memory than 64 KB. It would be an inefficient usage of virtual memory to allocate an entire segment of 64 KB for an application that requires much less than 64 KB of virtual memory since a large portion of the 64 KB would remain unused. For example, if the application only needed 2 KB of virtual memory, 62 KB of the virtual memory segment would remain unused.
Conventional heap managers allow for the allocation of virtual memory segments at a much finer granularity. A typical heap manager may allocate segments in a heap at a granularity of merely 8 bytes. In order to accomplish a more efficient usage of virtual memory, a heap manager instructs the virtual memory manager to allocate a relatively large virtual memory segment called a xe2x80x9cheapxe2x80x9d. As various applications require relatively small allocations of virtual memory, the heap manager makes the relatively small allocation of virtual memory from within the relatively large heap. The heap manager then keeps track of the location of the smaller segments within the larger heap as well as the process associated with that smaller allocation.
The conventional heap manager is very helpful in allowing for the more efficient use of memory space since the heap manager may allocate smaller increments of virtual memory within a heap. However, whenever a thread performs an allocation, a reallocation, or a deallocation of virtual memory within the heap, the entire heap is locked thereby prohibiting memory operations by other threads that also would use the heap. This locking operation often forces threads to wait until the heap is unlocked before operating on the heap.
One improvement to this conventional heap manager is implemented by a heap optimization module that causes the heap manager to create more than one heap. For example, the heap optimization module may cause the heap manager to create three more heaps than the number of processors in the system. Thus, in a two-processor system, the heap optimization module would cause the heap manager to create five heaps.
If a thread is to make a smaller allocation within a heap, the heap optimization module determines which heap is to receive the allocation. Specifically, the heap optimization module identifies a heap that is not locked. Then, the heap optimization module locks the identified heap and instructs the heap manager to make the smaller allocation in the identified heap. After the heap manager responds to the instruction by reporting the success or failure of the instructed allocation, the heap optimization module unlocks the identified heap. Thus, even if one of the heaps is locked, other threads may continue to make allocations within other unlocked heaps. In this manner, the heap optimization module distributes allocation to one of multiple heaps depending on which heaps are locked. This improves the speed of the system as compared to the conventional heap manager that only allocates a single heap in virtual memory.
In this manner, the heap optimization module identifies a specific heap in which to make an allocation. If the specific heap does not contain enough contiguous virtual memory addresses to make the requested allocation, the heap manager xe2x80x9cexpandsxe2x80x9d the heap. The heap manager increases the heap size by allocating an additional segment from virtual memory and assigning that segment to be part of the heap. The additional segment need not be contiguous with the initial heap segment since the heap manager is capable of tracking the location of the additional segments within virtual memory and associating those additional segments with the initial heap segment regardless of whether the heap segments are contiguous or not.
If further expansions for this heap were needed, then the added segment size would be doubled so long as there was sufficient contiguous space in virtual memory to do so.
For example, suppose the initial size of the heap was 16 MB and that the first expansion was 1 MB. The size of the heap would be initially expanded to 17 MB. The next expansion segment would be 2 MB thus increasing the heap size to 19 MB. The next expansion segment would be 4 MB, the next 8 MB, 16 MB, 32 MB, 64 MB, 128 MB, and so forth. Thus, the heap expansion algorithm in the heap manager may allocate extremely large additional segments.
Very little of the final very large expansion segment may, in fact, be used. For example, suppose that the final additional segment for a heap was 256 MB. It may be that only 1 MB of this segment is actually used to make allocations. This wastes a large amount of virtual memory, which cannot now be used by other threads within the process. This is compounded by the fact that the other heaps may be doing exactly the same sort of expansions.
Such wasting of virtual memory may be quite acceptable if there is sufficient virtual memory available. However, as mentioned above, in a 32-bit virtual memory addressing scheme, virtual memory is limited to 2 or 3 GB depending on how much virtual memory the operating system uses. In additional, the amount of physical memory in computer systems is tending to increase making it more possible to run out of virtual memory before running out of physical memory. In this context, wasting 255 MB of virtual memory may be undesirable, especially while other threads within the process are unsuccessfully searching for contiguous space in virtual memory in which to make an allocation. Thus, although the heap optimization module improves performance by allowing for heap allocations even if one or more heaps are locked, the heap optimization module may inefficiently use virtual memory space when numerous heap expansions are needed.
An additional problem with the conventional heap optimization module arises from the way that heaps are expanded as the virtual memory approaches complete use and thus as the size of the largest region of available contiguous virtual memory is reduced. There is one notable exception to the rule that expansions are doubled for each subsequent expansion to a given heap. Specifically, if there is simply not enough contiguous virtual memory left for the expansion anywhere in the virtual memory, the proposed expansion size is halved. This halving continues until either a contiguous virtual memory space is found of that size, or the size is already at a minimum acceptable size for an expansion. This minimum acceptable size may be, for example, the smallest virtual memory segment that the virtual memory manager is able to allocate (e.g., 64 KB).
Thus, as virtual memory is close to being completely consumed, the heap expansion sizes are reduced. From this relatively full state, virtual memory will typically be deallocated and released as processes finish using virtual memory. Since the smaller heap expansion segments still remain after the release of other segments of virtual memory, the smaller heap expansion segments may severely fragment the virtual memory thereby limiting future allocations in virtual memory.
Therefore, what are desired are methods and systems for performing heap allocations in a way that permits allocations to be made within a heap even if one or more heaps are currently locked, that more efficiently uses virtual memory, and that reduces the risk of virtual memory fragmentation.
The present invention permits allocations within heaps even if one or more heaps are currently locked. In addition, the present invention increases the efficiency of virtual memory usage and reduces the risk of virtual memory fragmentation. Instead of incrementally growing a full heap when it is used to make an allocation, the heap optimization module will look for another heap that may have available memory. If all the heaps are full, an entirely new heap will be created automatically and the allocation will be done from the newly created heap. The new heap is of a constant size, and furthermore, is added to the pool of available heaps. Thus, the new heap may be considered for heap allocations from any thread within the process. This reduces the risk that large portions of the heap segment will be unused and thus waste virtual memory. In addition, since the heaps are no longer expanded in potentially small increments, the risk of virtual memory fragmentation is reduced.
In accordance with the present invention, an initial number of non-growable heaps are allocated in the virtual memory. The number of initial heaps may be, for example, three more than the number of processors is the computer system. This initial number may be reconfigured by the user. A heap optimization module may create these initial heaps by calling on functions exposed by a heap manager.
Next, a determination is made that an allocation is to be made within a heap. For example, the heap optimization module may receive an instruction from an application that an allocation within a heap is to be made. If there is enough memory within the initial heaps to make the allocation necessitated by the received instruction, the memory is allocated from one of the initial number of non-growable heaps. However, if there is not enough virtual memory within the initial heaps to make the allocation necessitated by the received instruction, an entirely new heap is created for use in making the allocation necessitated by the received instruction.
Unlike conventional heap allocation methods, the heaps are not incrementally expanded with the incremental expansion size being related to the history of previous expansion sizes. Instead, entirely new heaps are created. The size of the new heaps may be independent of the heap allocation history. For example, instead of allocating a first new heap having a 1 Megabyte size, a second new heap having a 2 Megabyte size, and doubling the size of the expansion whenever an expansion is performed, the size of the new heaps may be relatively fixed size of, for example, 16 Megabytes for each new heap.
Since the heaps are entirely new, the heap is added to the pool of available heaps and thus may be considered by the heap optimization module when deciding which heap to make an allocation to. If all other heaps are full as was the case when the new heap was initially created, then the new heap would receive a higher proportion of new heap allocations. Thus, there would be a greater tendency for memory in the new heap to be used as compared to the conventional method of expanding existing heaps. In addition, since heap expansion is not performed, allocation of relatively small heap expansion segments is avoided. This reduces the risk of virtual memory fragmentation.
Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by the practice of the invention. The features and advantages of the invention may be realized and obtained by means of the instruments and combinations particularly pointed out in the appended claims. These and other features of the present invention will become more fully apparent from the following description and appended claims, or may be learned by the practice of the invention as set forth hereinafter.